package bTree.LeetCode;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;

public class 两棵二叉搜索树中的所有元素 {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer>list1=new ArrayList<>();
        List<Integer>list2=new ArrayList<>();
        save1(root1,list1);
        save2(root2,list2);
        List<Integer>res=new ArrayList<>();
        int left=0;
        int right=0;
        int size1 = list1.size();
        int size2 = list2.size();
        if (list1.isEmpty()){
            return list2;
        }
        if (list2.isEmpty()){
            return list1;
        }
        while (left<size1&&right<size2){
            Integer i1 = list1.get(left);
            Integer i = list2.get(right);
            if (i1<=i){
                res.add(i1);
                left++;
            }else {
                res.add(i);
                right++;
            }
        }
        if (left!=size1){
            for (int i=left;i<size1;i++){
                res.add(list1.get(i));
            }
        }
        if (right!=size2){
            for (int i=right;i<size2;i++){
                res.add(list2.get(i));
            }
        }
        return res;
    }

    private void save1(TreeNode root1, List<Integer> list1) {
        if (root1==null){
            return;
        }
        save1(root1.left, list1);
        list1.add(root1.val);
        save1(root1.right, list1);
    }

    private void save2(TreeNode root1, List<Integer> list1) {
        if (root1==null){
            return;
        }
        save1(root1.left, list1);
        list1.add(root1.val);
        save1(root1.right, list1);
    }
}